package lab.exec;

import java.util.Arrays;
import java.util.Random;

@SuppressWarnings("unused")
public class TestBalance {
	Random random = new Random();

	public int[] newRandomArray(int maxSize, int minSize) {
		int r = random.nextInt(maxSize - minSize);
		int[] a = new int[minSize + r];
		randomFillArray(a, 100);
		return a;
	}

	public void randomFillArray(int[] a, int maxValue) {
		for (int i = 0; i < a.length; i++) {
			int value = random.nextInt(maxValue);
			a[i] = value;
		}
	}

	public int sum(int[] a, int from, int to) {
		int sum = 0;
		for (int i = from; i < to; i++) {
			sum += a[i];
		}
		return sum;
	}

	public int std(int[] a) {
		int avg = sum(a, 0, a.length) / a.length;
		int sum = 0;
		for (int i = 0; i < a.length; i++) {
			int d = a[i] - avg;
			sum += d * d;
		}
		return (int) (Math.sqrt(sum / a.length));
	}

	public void balance(int[] a, int pc) {
		Arrays.sort(a);
		System.out.println(Arrays.toString(a));
		System.out.println("std = " + std(a));
		int from = 0;
		int to = a.length;
		while (from < to) {
			int avg = sum(a, from, to) / pc;
			int v = a[--to];
			StringBuilder sb = new StringBuilder();
			sb.append(v);
			int d = v - avg;
			int idx = from;
			for (int i = from; i < to - 2; i++) {
				int av = a[i];
				int bv = a[i + 1];
				if (bv < d) {
					continue;
				}
				if (av > d || (d - av > bv - d)) {
					idx = i;
				} else {
					idx = i + 1;
				}
				break;
			}
			while ((d = v - avg) < 0 && from < to) {
				int m = a[from++];
				v += m;
				sb.append(",").append(m);
			}
			System.out.println("avg = " + avg);
			System.out.println("p[" + (pc--) + "] = " + v + " {" + sb.toString() + "}");
		}
		while (pc > 0) {
			System.out.println("p[" + (pc--) + "] = ");
		}
	}

	int[] buf = new int[10];
	int startIndex = 0;

	private int selectValue(int[] src, int idx, int size, boolean rm) {
		if (buf.length <= size) {
			int[] temp = new int[buf.length + 1];
			System.arraycopy(buf, 0, temp, 0, size);
			buf = temp;
		}
		buf[size] = src[idx];
		if (rm) {
			for (int i = idx; i > startIndex; i--) {
				src[i] = src[i - 1];
			}
			startIndex++;
		} else {
			src[idx] = -1;
		}
		return ++size;
	}

	private int selectNext(int[] src, int idx, int avg) {
		int s = src[idx];
		if (s < 0) {
			return -1;
		}
		int size = 0;
		size = selectValue(src, idx, size, false);
		if (s >= avg || idx == startIndex) {
			return size;
		} else if (idx == startIndex + 1) {
			return selectValue(src, --idx, size, true);
		}
		idx--;
		int n1 = -1;
		int n2 = -1;
		while (idx >= startIndex) {
			int i1 = idx;
			if (n2 >= 0) {
				n1 = n2;
			} else {
				n1 = src[i1];
			}
			int i2 = i1 - 1;
			if (i2 >= startIndex) {
				n2 = src[i2];
			} else {
				n2 = -1;
			}
			int d1 = n1 + s - avg;
			int d2 = n2 + s - avg;
			if (d1 >= 0 && d2 <= 0) {
				if (d1 + d2 <= 0 || n2 < 0) {
					return selectValue(src, i1, size, true);
				} else {
					return selectValue(src, i2, size, true);
				}
			}
			if (d1 < 0) {
				s += n1;
				size = selectValue(src, i1, size, true);
				idx = i1;
			} else {
				idx = i2;
			}
		}
		return size;

	}

	public int balance_S(int[] src, int pc) {
		startIndex = 0;
		Arrays.sort(src);
		// System.out.println(Arrays.toString(src));
		// int avg = sum(src, 0, src.length) / pc;
		// System.out.println("pc= " + pc + ", avg= " + avg);
		int[][] ab = new int[pc][];
		int pi = 0;
		for (int i = src.length - 1; i >= startIndex; i--) {
			int avg = sum(src, startIndex, i + 1) / (pi >= pc ? pc : pc - pi);
			int size = selectNext(src, i, avg);
			if (size > 0) {
				int[] a = new int[size];
				System.arraycopy(buf, 0, a, 0, size);
				if (pi >= pc) {
					for (int j = 0; j < a.length; j++, pi++) {
						int ri = pi % pc;
						int[] t = ab[ri];
						int[] _t = new int[t.length + 1];
						System.arraycopy(t, 0, _t, 0, t.length);
						_t[t.length] = a[j];
						ab[ri] = _t;
					}
				} else {
					ab[pi++] = a;
				}
			}
		}
		while (pi < pc) {
			ab[pi++] = new int[0];
		}
		int[] v = new int[ab.length];
		for (int i = 0; i < ab.length; i++) {
			int[] a = ab[i];
			v[i] = sum(a, 0, a.length);
			System.out.println("pc[" + (i + 1) + "] = <" + v[i] + ">" + Arrays.toString(a));
		}
		Arrays.sort(v);
		System.out.println("max : " + (v[v.length - 1] - v[0]));
		return std(v);
	}

	public void balance_M(int[] a, int pc) {
		Arrays.sort(a);
		// System.out.println(Arrays.toString(a));
		int avg = sum(a, 0, a.length) / pc;
		int n = a.length % pc == 0 ? a.length / pc : (a.length / pc + 1);
		// System.out.println("pc= " + pc + ", n= " + n + ", avg= " + avg);
		int[][] ab = new int[pc][n];
		int pi = 0;
		int s = 1;
		int ni = 0;
		for (int i = 0; i < a.length; i++) {
			if (pi == pc) {
				s = -1;
				pi += s;
				ni++;
			} else if (pi == -1) {
				s = 1;
				pi += s;
				ni++;
			}
			ab[pi][ni] = a[i];
			pi += s;
		}
		// for (int i = 0; i < ab.length; i++) {
		// System.out.println("pc[" + (i + 1) + "] = <" + sum(ab[i], 0,
		// ab[i].length) + ">" + Arrays.toString(ab[i]));
		// }
	}

	public int balance_R(int[] src, int pc) {
		Arrays.sort(src);
		System.out.println(Arrays.toString(src));
		int avg = sum(src, 0, src.length) / pc;
		System.out.println("pc= " + pc + ", avg= " + avg);
		int[] sa = new int[pc];
		int[] seq = new int[pc];
		int[][] ab = new int[pc][0];
		for (int i = 0; i < pc; i++) {
			seq[i] = i;
		}
		for (int i = src.length - 1; i >= 0; i--) {
			int idx = seq[0];
			sa[idx] = sa[idx] + src[i];
			int length = ab[idx].length;
			int[] _a = new int[length + 1];
			System.arraycopy(ab[idx], 0, _a, 0, length);
			_a[length] = src[i];
			ab[idx] = _a;
			for (int j = 0; j < pc - 1; j++) {
				if (sa[seq[j]] <= sa[seq[j + 1]]) {
					break;
				} else {
					int t = seq[j];
					seq[j] = seq[j + 1];
					seq[j + 1] = t;
				}
			}
		}
		int[] v = new int[ab.length];
		for (int i = 0; i < ab.length; i++) {
			int[] a = ab[i];
			v[i] = sum(a, 0, a.length);
			System.out.println("pc[" + (i + 1) + "] = <" + v[i] + ">" + Arrays.toString(a));
		}
		Arrays.sort(v);
		System.out.println("max : " + (v[v.length - 1] - v[0]));
		return std(v);
	}

	public int balance_RS(int[] src, int pc) {
		Arrays.sort(src);
		System.out.println(Arrays.toString(src));
		int avg = sum(src, 0, src.length) / pc;
		System.out.println("pc= " + pc + ", avg= " + avg);
		int[] sum = new int[pc];
		int[] idx = new int[pc];
		for (int i = 0; i < pc; i++) {
			idx[i] = i;
		}
		int count = src.length % pc == 0 ? src.length / pc : src.length / pc + 1;
		int[][] ab = new int[pc][count];
		for (int ci = 0, ai = 0; ci < count; ci++) {
			for (int i = 0; i < idx.length - 1; i++) {
				for (int j = i; j < idx.length - 1; j++) {
					int v1 = sum[idx[j]];
					int v2 = sum[idx[j + 1]];
					if (v1 < v2) {
						int t = idx[j];
						idx[j] = idx[j + 1];
						idx[j + 1] = t;
					}
				}
			}
			for (int i = 0; i < idx.length && ai < src.length; i++, ai++) {
				sum[idx[i]] += src[ai];
				ab[idx[i]][ci] = src[ai];
			}
		}
		int[] v = new int[ab.length];
		for (int i = 0; i < ab.length; i++) {
			int[] a = ab[i];
			v[i] = sum(a, 0, a.length);
			System.out.println("pc[" + (i + 1) + "] = <" + v[i] + ">" + Arrays.toString(a));
		}
		Arrays.sort(v);
		System.out.println("max : " + (v[v.length - 1] - v[0]));
		return std(v);
	}

	public int test() {
		int[] a = newRandomArray(200, 100);
		return balance_S(a, 20);
	}

	public void testStd() {
		int[] a = new int[200];
		for (int i = 0; i < a.length; i++) {
			a[i] = i == 0 ? 100 : 0;
		}
		System.out.println(balance_RS(a, 20));
	}

	public static void main(String[] args) {
		long time = System.currentTimeMillis();
		TestBalance tb = new TestBalance();
		// tb.testStd();
		int[] v = new int[1000];
		for (int i = 0; i < v.length; i++) {
			v[i] = tb.test();
		}
		Arrays.sort(v);
		System.out.println("max : " + (v[v.length - 1] - v[0]));
	}
}
